package kyssion.leetcode.num101_150;

import kyssion.leetcode.util.ListNode;
import kyssion.leetcode.util.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class code109_有序链表转化二叉搜索树 {
    public TreeNode sortedListToBST(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while(head!=null){
            list.add(head.val);
            head = head.next;
        }
        return ans(list,0,list.size()-1);
    }

    private TreeNode ans(List<Integer> list, int start, int end) {
        if(start>end){
            return null;
        }
        // 0 1 0
        int midle = (start+end)>>1;
        TreeNode treeNode = new TreeNode(list.get(midle));
        treeNode.left = ans(list,start,midle-1);
        treeNode.right = ans(list,midle+1,end);
        return treeNode;
    }


    /**
     * 二叉树搜索中间项  o n/2时间复杂度  使用双指针实现
     * @param head
     * @return
     */
    public TreeNode sortedListToBST2(ListNode head) {
        // 刚做过二叉搜索数转换为有序链表
        // 首先要找到中间的节点
        if(head == null)
            return null;
        if(head.next == null)
            return new TreeNode(head.val);
        ListNode slow = head;
        ListNode fast = head.next;
        ListNode pre = head;
        while(fast != null && fast.next != null){
            pre =  slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.right = sortedListToBST(slow.next);
        pre.next = null;
        if(slow == head)
            root.left = null;
        else
            root.left = sortedListToBST(head);
        return root;
    }
}
